package com.monkey.luffer.springboot.demo.basis.example;

import java.util.ArrayList;

/**
 * @Author: dengkaibing
 * @Description: 最大堆实现
 * @Date: 2021/1/5 14:34
 * @company 甜橙金融
 * @Version: 1.0
 */
public class MinHeap<E extends Comparable<E>> {
    public ArrayList<E> data;

    //初始化容量
    public MinHeap(int capacity) {
        data = new ArrayList<E>(capacity);
    }

    public MinHeap() {
        data = new ArrayList<>();
    }

    public int size() {
        return data.size();
    }

    //进堆
    public void add(E e) {
        data.add(e);
        int index = data.size() - 1;
        while (index > 0) {
            int parentIndex = (index - 1) >> 1;
            if (parentIndex >= 0 && e.compareTo(data.get(parentIndex)) < 0) {
                E currentData = data.get(parentIndex);
                data.set(parentIndex, e);
                data.set(index, currentData);
            }
            index = parentIndex;
        }
    }

    //出堆
    public E poll() {
        E e = data.get(0);
        E current = data.get(data.size() - 1);
        data.set(0, current);
        data.remove(data.size() - 1);
        int index = 0;
        while (index < data.size()) {
            int leftIndex = (index << 1) + 1;
            int rightIndex = (index << 1) + 2;
            //无孩子节点
            if (leftIndex >= data.size()) {
                break;
                //无右孩子节点
            } else if (rightIndex >= data.size()) {
                E currentLeft = data.get(leftIndex);
                if (current.compareTo(currentLeft) >0) {
                    data.set(index, currentLeft);
                    data.set(leftIndex, current);
                    index = leftIndex;
                }else{
                    break;
                }
                //左右孩子节点都存在取值小的节点交换
            } else {
                if (data.get(leftIndex).compareTo(data.get(rightIndex)) < 0) {
                    data.set(index, data.get(leftIndex));
                    data.set(leftIndex, current);
                    index = leftIndex;
                } else {
                    data.set(index, data.get(rightIndex));
                    data.set(rightIndex, current);
                    index = rightIndex;
                }
            }

        }
        return e;
    }

    public E peek() {
        return data.get(0);
    }

}
